This disclosure relates to systems (e.g., methods and/or apparatus) for performing fast Fourier transform (“FFT”) operations and/or inverse fast Fourier transform (“IFFT”) operations. For convenience herein (e.g., to simplify the discussion) the phrase fast Fourier transform and the acronym FFT will generally be used as generic terms for both fast Fourier transform (FFT) operations and inverse fast Fourier transform (IFFT) operations.
More specifically, this disclosure relates to FFT operations of the type sometimes known as “radix 4n2m FFT.” In the expression “4n2m,” the parameter (exponent) n is a positive integer greater than zero (i.e., n can have any positive integer value such as 1, 2, 3, 4, . . . ), and the parameter (exponent) m can have either the value 0 or the value 1. If m=0 in a particular case, then the expression “radix 4n2m” can be simplified to “radix 4n” (because 20=1). On the other hand, if m has a value of one, then the “radix 4n2m FFT” may sometimes be referred to as a “mixed radix FFT” or the like. Despite the possibility of simplifying “radix 4n20)” to “radix 4n,” it will be understood that references to “radix 4n2m” herein generally include the “radix 4n20” case, unless the “radix 4n20” case is expressly excluded (e.g., by expressly referring to a “mixed radix 4n2m FFT”, by specifying that m has a value of 1, or the like).
As is well known to those skilled in this art, radix 4n2m FFT operations may be characterized by including “butterfly” operations that are performed on four inputs per butterfly operation. This is distinct or different from radix 2n FFT operations, which typically employ only “butterfly” operations that are performed on only two inputs per butterfly operation.
By way of further preliminaries, it will be understood that throughout this disclosure all “information,” “data,” “samples,” “inputs,” “outputs,” “values,” “addresses,” and/or the like that are referred to are represented by electrical signals that are processed by electronic circuitry. Thus references to “data,” “samples,” “inputs,” “outputs,” “values,” “addresses,” and/or the like herein will be understood to always mean “data signals,” “sample signals,” and/or the like, even through the word “signal” or “signals” may not be expressly stated in all instances. Similarly, it will be understood that the FFT operations disclosed or otherwise discussed herein are always performed in electronic circuitry, some illustrative embodiments of at least relevant portions of such electronic circuitry being shown and described later in this disclosure.
At least some techniques for performing radix 4n2m FFT operations include a need for reordering data items that are part of the FFT operation. For example, there may be a need to reorder data items output by the FFT operation (e.g., frequency domain data signal items or time domain data signal items). A typical way to implement such data reordering is to use two memory banks, the memory banks being used alternately to store successive complete sets of the data items in the starting order, and the memory bank that is not currently accepting new data items being addressed to retrieve the previously stored data items in the desired final order. Requiring two memory banks for this purpose can consume a relatively large amount of memory, and it may also increase latency in (i.e., delay through) the FFT circuitry.